package Hard;
// 4.寻找两个有序数组的中位数
public class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        if(length==1){
            try{
                return nums1[0];
            }catch (Exception e){
                return nums2[0];
            }
        }
        if (nums1.length == 0) {
            int count;
            for (count = 0; count < nums2.length / 2; count++)
                ;
            if (length % 2 != 0)
                return nums2[count];
            else
                return (double) (nums2[count] + nums2[count - 1]) / 2;
        }
        if (nums2.length == 0) {
            int count;
            for (count = 0; count < nums1.length / 2; count++)
                ;
            if (length % 2 != 0)
                return nums1[count];
            else
                return (double) (nums1[count] + nums1[count - 1]) / 2;
        }
        boolean jishu = false;
        if (length % 2 != 0)
            jishu = true;
        int count = 0;
        int i = 0, j = 0;
        int k = -1;//k==0代表最后一次是i自增了，k==1代表最后一次是j自增了
        while (count < length / 2) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    i++;
                    count++;
                    k=0;
                } else {
                    j++;
                    count++;
                    k=1;
                }
            }
            if (i == nums1.length || j == nums2.length)
                break;
        }
        if (count == length / 2) {
            //正好有一个数组被遍历完的同时，找到了第count个数
            if (i == nums1.length) {
                if (jishu){
                    if(k==0)
                        return nums1[i-1]<nums2[j]?nums2[j]:nums1[i-1];
                    else
                        return nums2[j-1]<nums1[i]?nums1[i]:nums2[j-1];
                }
                else
                    return (double) (nums1[i-1] + nums2[j]) / 2;
            }else if(j==nums2.length){
                if (jishu)
                    if(k==0)
                        return nums1[i-1]<nums2[j]?nums2[j]:nums1[i-1];
                    else
                        return nums2[j-1]<nums1[i]?nums1[i]:nums2[j-1];
                else
                    return (double) (nums1[i] + nums2[j-1]) / 2;
            }
            if (jishu)
                return nums1[i] < nums2[j] ? nums1[i] : nums2[j];
            else {
                int a = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
                if(k==0)
                    i--;
                if(k==1)
                    j--;
                int b = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
                return (double) (a + b) / 2;
            }
        }
        //因为一个数组率先结束而终止循环的情况
        if (i == nums1.length) {
            while (count < length / 2) {
                j++;
                count++;
            }
            if (jishu)
                return nums2[j];
            else return (double) (nums2[j] + nums2[j-1]) / 2;
        }
        while (count < length / 2) {
            i++;
            count++;
        }
        if (jishu)
            return nums1[i];
        else return (double) (nums1[i] + nums1[i - 1]) / 2;
    }
}
